package com.zlei.code.binaryTree.traversal;

import com.zlei.code.binaryTree.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 二叉树的层序遍历
 * https://blog.csdn.net/weixin_40145104/article/details/96358258
 * @Author leizhang76
 * @Date 2021/2/23 10:58
 */
public class Sequence {

    /**
     * 二叉树的层序遍历，从上到下打印二叉树，每一层节点从左至右输出
     * 借助队列先进先出原则就可以实现。
     * 通过两个队列，其中一个作为辅助队列
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> print(TreeNode pRoot){
        LinkedList<TreeNode> queue1=new LinkedList<>();
        ArrayList<ArrayList<Integer>> arrays=new ArrayList<>();
        if (pRoot!=null){
            queue1.add(pRoot);
            while (!queue1.isEmpty()){
                LinkedList<TreeNode> queue2=new LinkedList<>();
                ArrayList<Integer> array=new ArrayList<>();
                while (!queue1.isEmpty()){
                    TreeNode poll = queue1.poll();
                    if (poll.left!=null){
                        queue2.add(poll.left);
                    }
                    if (poll.right!=null){
                        queue2.add(poll.right);
                    }
                    array.add(poll.val);
                }
                arrays.add(array);
                queue1=queue2;
            }
        }
        return arrays;
    }

    /**
     *二叉树的层序遍历
     * 通过一个队列实现，以一个int类型的变量记录每一层节点数
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> print1(TreeNode pRoot){
        LinkedList<TreeNode> queue=new LinkedList<>();
        ArrayList<ArrayList<Integer>> arrays=new ArrayList<>();
        if (pRoot!=null){
            queue.add(pRoot);
            int len=1;
            while (!queue.isEmpty()){
                int value=0;
                ArrayList<Integer> array=new ArrayList<>();
                for (int i = 0; i < len; i++) {
                    TreeNode poll = queue.poll();
                    if (poll.left!=null){
                        queue.add(poll.left);
                        value++;
                    }
                    if (poll.right!=null){
                        queue.add(poll.right);
                        value++;
                    }
                    array.add(poll.val);
                }
                arrays.add(array);
                len=value;
            }
        }
        return arrays;
    }

    /**
     * 将二叉树按照之字形打印，即奇数行从左往右，偶数行从右往左
     * 那么可以借助栈先进后出的特点实现之字形打印二叉树，设两个栈stack1,stack2；stack2为辅助栈
     * 奇数行，从左往右打印：当前节点的
     * @param pRoot
     * @return
     */
    public ArrayList<ArrayList<Integer>> print3(TreeNode pRoot){
        ArrayList<ArrayList<Integer>> arrays=new ArrayList<>();
        Stack<TreeNode> stack1=new Stack<>();
        if (pRoot!=null){
            stack1.push(pRoot);
            //b=true的时候从左到右，b=false的时候从右到左
            boolean b=true;
            while (!stack1.isEmpty()){
                ArrayList<Integer> array=new ArrayList<>();
                Stack<TreeNode> stack2=new Stack<>();
                if (b){//从左到右
                    while (!stack1.isEmpty()){
                        TreeNode pop = stack1.pop();
                        if (pop.left!=null){
                            stack2.push(pop.left);
                        }
                        if (pop.right!=null){
                            stack2.push(pop.right);
                        }
                        array.add(pop.val);
                    }
                }else {//从右到左
                    while (!stack1.isEmpty()){
                        TreeNode node=stack1.pop();
                        if (node.right!=null){
                            stack2.push(node.right);
                        }
                        if (node.left!=null){
                            stack2.push(node.left);
                        }
                        array.add(node.val);
                    }
                }
                b=!b;
                arrays.add(array);
                stack1=stack2;
            }
        }
        return arrays;
    }


}




















